package com.tgy.dynamic.programming;

/**
 * @Author: tgy
 * @Date: 2020/11/14 7:46 下午
 *
 * longest common substring 最长公共子串
 */
public class LCSubString {


    /**
     * 一维数组实现
     * @param left
     * @param right
     * @return
     */
    public int lcsubString(String left, String right) {

        char[] leftChars = left.toCharArray();
        char[] rightChars = right.toCharArray();

        if (rightChars.length > leftChars.length) {

            char[] tmp = leftChars;
            leftChars = rightChars;
            rightChars = tmp;
        }

        int[] dp = new int[rightChars.length + 1];

        int max = 0,curV = 0,preV;
        for (int i = 1; i <= leftChars.length; i++) {

            preV = 0;
            for (int j = 1; j < rightChars.length; j++) {

                preV = curV;
                curV = dp[j];
                if (leftChars[i - 1] == rightChars[j - 1]) {

                    dp[j] = preV + 1;
                    if (dp[j] > max) {
                        max = dp[j];
                    }
                }else {

                    dp[j] = 0;
                }
            }

        }
        return max;
    }

    /**
     * 二维数组实现
     * @param left
     * @param right
     * @return
     */
//    public int lcsubString(String left, String right) {
//
//        char[] leftChars = left.toCharArray();
//        char[] rightChars = right.toCharArray();
//
//        int[][]dp = new int[leftChars.length + 1][rightChars.length + 1];
//
//        int max = 0;
//        for (int i = 1; i <= leftChars.length; i++) {
//
//            for (int j = 1; j < rightChars.length; j++) {
//
//                if (leftChars[i - 1] == rightChars[j - 1]) {
//
//                    dp[i][j] = dp[i - 1][j-1] + 1;
//                    if (dp[i][j] > max) {
//
//                        max = dp[i][j];
//                    }
//                }else {
//
//                    dp[i][j] = 0;
//                }
//            }
//
//        }
//        return max;
//    }
}
